package dataStructs.huffman;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author Jonny Long
 * @date 2021/3/9 15:49
 */
public class HuffmanTree {
    private HuffmanNode root;

    public HuffmanNode getRoot() {
        return root;
    }

    public void setRoot(HuffmanNode root) {
        this.root = root;
    }

    // 先序遍历
    public void preOrder(HuffmanNode current) {
        if (current != null) {
            System.out.println(current);
            preOrder(current.left);
            preOrder(current.right);
        }
    }

    /**
     * 创建Huffman树
     * @param arr 需要创建成哈夫曼树的数组
     * @return 创建好后的赫夫曼树的root结点
     */
    public static HuffmanNode createHuffmanTree(int[] arr){
        ArrayList<HuffmanNode> nodes = new ArrayList<>();
        for(int value: arr){
            nodes.add(new HuffmanNode(value));
        }
        while(nodes.size() > 1) {

            //排序 从小到大
            Collections.sort(nodes);

            System.out.println("nodes =" + nodes);

            //取出根节点权值最小的两颗二叉树
            //(1) 取出权值最小的结点（二叉树）
            HuffmanNode leftNode = nodes.get(0);
            //(2) 取出权值第二小的结点（二叉树）
            HuffmanNode rightNode = nodes.get(1);

            //(3)构建一颗新的二叉树
            HuffmanNode parent = new HuffmanNode(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            //(4)从ArrayList删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //(5)将parent加入到nodes
            nodes.add(parent);
        }
        //返回哈夫曼树的root结点
        return nodes.get(0);
    }
}
